Source Coding

Definitions: Part I

• $ \mathcal{D}^{*} $: The set of finite-length strings of symbols from D-ary(D symbols) alphabet $ \mathcal{D} $.

$$ \mathcal{D}^{*} = \mathcal{D} \cup \mathcal{D}^{2} \cup \mathcal{D}^{3} \cup \cdots $$

• Code / Source Code:

$$ \begin{aligned} C : \mathcal{X} &\mapsto \mathcal{D}^{*} \end{aligned} $$

• Codeword:

$$ \begin{aligned} C(x) &\in \mathcal{D}^{*} &\forall x \in \mathcal{X} \end{aligned} $$

• Length of a Codeword:

$$ \ell(x) $$

• Code is Nonsingular ⟺ Code is Injective:

$$ \begin{aligned} x \neq \tilde{x} \Rightarrow C(x) \neq C(\tilde{x}) \end{aligned} $$

Definitions: Part I

• Extension of a Code: Finite length strings of $ \mathcal{X} $ to finite length strings of $ \mathcal{D} $. $$ \begin{aligned} C: \mathcal{X}^{*} &\mapsto \mathcal{D}^{*} \\ C(x_1 \cdots x_n) &= C(x_1) \cdots C(x_n) \end{aligned} $$

• Code is Uniquely Decodable if Its extension is nonsingular:

$$ \begin{aligned} x_1 \cdots x_n \neq \tilde{x}_1 \cdots \tilde{x}_n \Longrightarrow C(x_1) \cdots C(x_n) \neq C(\tilde{x}_1) \cdots C(\tilde{x}_n) \end{aligned} $$

• Code is Prefix-Free if no codeword is prefix of another codeword, and it is called Prefix Code or Instantaneous Code.

by Jon